import java.util.Comparator;

public class QuickSort {

    public static <T> void quickSort(T[] a, Comparator<? super T> c) {

        quickSort(a, c, 0, a.length);

    }

    public static <T> void quickSort(T[] a, Comparator<? super T> c, int p, int r) {

        if (p < r) {
            int q = partition(a, c, p, r);
            quickSort(a, c, p, q - 1);
            quickSort(a, c, q + 1, r);
        }

    }

    public static <T> int partition(T[] a, Comparator<? super T> c, int p, int r) {

        T t = a[r - 1];
        int i = p - 1;
        for (int j = p; j < r - 1; j++) {
            if (c.compare(a[j], t) <= 0) {
                i++;
                T tmp = a[i];
                a[i] = a[j];
                a[j] = tmp;

            }

        }

        T tmp = a[i + 1];
        a[i + 1] = a[r - 1];
        a[r - 1] = tmp;

        return i + 1;
    }

    /**
     * @param args
     */
    public static void main(String[] args) {

        Integer[] temp = new Integer[] {
            2, 8, 7, 1, 3, 5, 6, 4
        };

        quickSort(temp, new Comparator<Integer>() {

            @Override
            public int compare(Integer o1, Integer o2) {

                return o1 - o2;
            }
        });

        for (int i : temp) {
            System.out.print(i + " ");
        }
        System.out.println();
    }

}
